class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        # import copy
        # ret = copy.deepcopy(head)
        # return ret

        if not head:
            return None
        # 复制一个相同的值的节点，eg:1>2>3>none  >>>>  1>1(新)>2>2(新)>3>3(新)>none
        ptmp = head
        while ptmp:
            node = Node(ptmp.val)
            node.next = ptmp.next
            ptmp.next = node
            ptmp = node.next

        #将以前的random，赋给新的节点的random
        ptmp = head
        while ptmp:
            if  ptmp.random:
                ptmp.next.random = ptmp.random.next
            ptmp = ptmp.next.next
        #断开连接
        ptmp = head
        newhead = ptmp.next
        curnewhead = newhead
        while ptmp:
            if curnewhead.next:
                ptmp.next = curnewhead.next
                curnewhead.next = ptmp.next.next
                curnewhead = curnewhead.next
            ptmp = ptmp.next
        return newhead
if __name__ == '__main__':
    n1 = Node(1)
    n2 = Node(2)
    n3 = Node(3)
    n4 = Node(4)
    n5 = Node(5)
    n1.next = n2
    n1.random = n3
    n2.next = n3
    n2.random = n1
    n3.next = n4
    n4.next = n5
    n5.random =n1
    s =Solution()
    m = s.copyRandomList(n1)
    while m :
        print(m.val)
        m = m.next


